This invention relates primarily to a class of digital communication systems known as asynchronous transfer mode (ATM) switching systems and more generally to intercomputer communications architectures. The invention more specifically relates to systems and methods for removing undeliverable cells in an output routing table within an ATM network.
A building block in a switch-fabric architecture ATM switch system is a structure known as a switch element. A switch element provides packet signal routing from one of a plurality of input ports to one or more of a plurality of output ports by maintaining an array of crosspoints for connecting any input port to any output port. Switch elements may be aggregated in various patterns to provide arbitrarily large N by N possible interconnection of input ports to output ports.
Another building block in a switch-fabric architecture ATM switch system is a structure known as a routing table (RT). In an ATM switch there generally is functionally an output routing table (ORT) and an input routing table (IRT).
One solution to the problem of buffering cells as they flow through various switch devices, including RTs, is the use of a shared pool of memory for storing queued cells. A shared pool more effectively utilizes available memory. However, a shared pool is also more susceptible to various types of "blocking," wherein cells which are delayed within the shared pool block the passage of other cells through the device when these other cells might otherwise be able to be transmitted through a device.
Increasing demands for communications speed and capacity have created a need for a higher performance ATM architecture as described in 60/033,029. This architecture differs from an earlier architecture designed by one of the inventors of the present invention in that the primary shared pool memory areas are associated with an input routing table (IRT) and output routing table (ORT). Shared pool buffer memories associated with individual switch elements are generally used only when handling multicast traffic. The new architecture is different also in that it provides for a number of virtual outputs (VOs) for each output line from an ORT and a number of virtual inputs (VIs) for each input line to an IRT. In one specific embodiment, the ORT and IRT are combined into a single device referred to as a Quad Routing Table (QRT). The QRT may be used in connection with a switch fabric constructed of switch elements (SEs) as described in earlier applications or may be used in connection with a switch fabric made up of update quad switch elements (QSEs) as described in 60/033,029.
In various reference materials and in the 60/029,543 application, a VO of a QRT connects to a PHY. A PHY (for PHYsical connection) generally represents a connection to a different physical device. In a telephone network, the different PHYs might be trunk lines to different cities; in a wide-area-network router, the PHYs might be connecting to different floors in a building; in a local-area-network switch, the PHYs might be different individual workstations. Throughout this document, the term VO should be understood to be connected to a PHY, unless the context requires otherwise.
A particular problem that can arrive in a switch architecture with VOs and some type of shared buffer space is what happens when one of the physical connections to which a VO is connected unexpectedly becomes disabled or broken. In general, it will take some time for higher layer communication protocols to detect that a VO cannot receive data. During that time, cells queued for the disabled VO may fill up the buffer pool in the ORT, thus degrading the performance of delivery of cells directed to other VOs which remain operational. Furthermore, in many ATM applications, such as live telephone or video, once a cell has been delayed even a short time from when it was expected, the cell effectively becomes stale and delivery of stale cells would be worse than non-delivery of those cells. In various references in the art, identifying and eliminating from an ATM system stale or undeliverable cells is referred to as cell flushing.
Some prior-art ATM architectures do not have specific mechanisms for detecting and flushing cells in an ORT that are directed to a particular disabled VO. If one of the VOs breaks, traffic to that VO back up, disrupting traffic to other VOs of the ORT. In this case, the only alternative is to reset the entire ORT, thereby deleting all of the cells that are pending in the ORT.
A different technique is to have a mechanism within the ORT that accurately knows the rate that a VO is expected to be able to receive cells. In this technique, if one of the VOs stops accepting cells, the ORT can force that VO to accept cells anyway at the rate it would expect the VO to normally accept cells. This solution is complex to implement, however, in terms of both hardware and processing of cells.
A different technique is to include a special flushing dequeue routine, different from the normal dequeue mechanism, for removing undeliverable or late cells. This solution is also complex to implement and expensive in terms of gates and processing.
What is needed is a method or apparatus for an ATM architecture having shared resources in an output routing table that allows the ORT to effectively detect and delete cells directed to physical connections or virtual outputs that are disabled.